/*
 * @lc app=leetcode.cn id=1631 lang=cpp
 *
 * [1631] 最小体力消耗路径
 */

// @lc code=start
class Solution
{
public:
    struct Cell
    {
        int x, y;
    };
    int m, n;
    int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    int bfs(int cost, vector<vector<int>> &heights)
    {
        vector<vector<int>> mark(m, vector<int>(n, 0));
        queue<Cell> q;
        q.push({0, 0});
        mark[0][0] = 1;
        while (!q.empty())
        {
            Cell curr = q.front();
            q.pop();
            if (curr.x == m - 1 && curr.y == n - 1)
            {
                return 1;
            }
            for (auto [dx, dy] : dirs)
            {
                int nx = curr.x + dx;
                int ny = curr.y + dy;
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || mark[nx][ny] == 1)
                {
                    continue;
                }
                if (abs(heights[curr.x][curr.y] - heights[nx][ny]) <= cost)
                {
                    mark[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
        }

        return 0;
    }

    int minimumEffortPath(vector<vector<int>> &heights)
    {
        m = heights.size();
        n = heights[0].size();
        int l = 0, r = 10e6, mid;
        while (l < r)
        {
            mid = l + ((r - l) >> 1);
            if (bfs(mid, heights))
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        return l;
    }
};
// @lc code=end
